package array;

public class leetCode312_maxCoins {
    // 定义dp[i][j]为 [i,j]的闭区间所能获得硬币的最大数量.
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] point = new int[n + 2];
        for (int i = 0; i < n; i++) {
            point[i + 1] = nums[i];
        }
        point[0] = 1;
        point[n + 1] = 1;
        int[][] dp = new int[n + 1][n + 2];
        for (int i = n - 1; i >= 0 ; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][k] + point[k] * point[i] * point[j] + dp[k][j]);
                }
            }
        }
        return dp[0][n + 1];




    }
}
